package linkedList;

/**
 * 双向链表
 */
public class DoubleLinkedList {
    //当前的有效节点个数
    private int size;
    //当前的头节点
    private doubleNode head;
    //当前的尾节点、
    private doubleNode tail;

    /**
     * 删除链表中所有值为val的节点
     */
    public void removeAllVal(int val){
        for (doubleNode x=head;x!=null;) {
            if (x.val==val){
                //此时x是待删除的点，同时保存一下x的后继节点的地址
                doubleNode successor=x.next;
                removeNode(x);
                x=successor;
            }else{
                //此时x已经不是待删除的点了，这是让for循环继续向下判断
                x=x.next;
            }
        }
    }

    /**
     * 删除链表中第一和值为val的节点
     */
    public void removeValOnce(int val){
        for (doubleNode x=head;x!=null;x=x.next) {
            if (x.val==val){
                removeNode(x);
                break;
            }
        }
    }

    /**
     * 删除链表中索引为index的节点
     * @param index
     */
    public void removeIndex(int index){
        //判断index是否合法
        if (judgeIndex(index)){
            doubleNode node=findNode(index);
            removeNode(node);
        }else{
            System.err.println("index不在范围内");
        }
    }
    /**
     * 删除当前链表中的node节点
     * @param node
     */
    public void removeNode(doubleNode node){
        doubleNode prev=node.prev;
        doubleNode successor=node.next;
        //1.先处理node的前半部分
        //判断前驱是否为空，为空则是删除头节点
        if (prev==null){
            head=successor;
        }else{
            //此时前驱不为空
            prev.next=successor;
            node.prev=null;
        }
        //2.在处理node的后半部分
        //判断后继节点是否为空，相当于删除尾节点
        if (successor==null){
            tail=prev;
        }else{
            //此时后继节点不为空
            successor.prev=prev;
            node.next=null;
        }
        size--;
    }
    /**
     * 根据索引值寻找对应的节点
     * @param index
     * @return
     */
    private doubleNode findNode(int index){
        doubleNode x=null;
        if (index<size){
            x=head;
            for (int i = 0; i <index; i++) {
                x=x.next;
            }
        }else{
            x=tail;
            for (int i =index; i <size-1; i--) {
                x=x.prev;
            }
        }return x;
    }


    /**
     * 查找索引为index的节点值，返回节点值
     * @param index
     * @return
     */
    public int  get(int index){
        //判断index的合法性
        if (judgeIndex(index)){
          doubleNode x=findNode(index);
          return x.val;
        }

        return -1;
    }
    /**
     * 修改索引为index位置的节点值为val，返回修改前的值
     * @param index
     * @param val
     * @return
     */
    public int set(int index,int val){
        //判断index的合法性
        if (judgeIndex(index)){
            doubleNode x=findNode(index);
            int oldVal=x.val;
            x.val=val;
            return oldVal;

        }
        return -1;
    }
    /**
     * 判断index是否合法
     * @param index
     * @return
     */
    private boolean judgeIndex(int index){
        if (index<0||index>=size){
            return false;
        }
        return true;
    }

    /**
     * 双向链表在索引位置插入值为val的节点
     * @param index
     * @param val
     */
    public void add(int index,int val){
        //判断index是否合法
        if (index<0||index>size){
            System.err.println("index不在范围内");
            return;
        }
        if (index==0){
            //相当于头插
            addFirst(val);
        }else if (index==size){
            //相当于尾插
            addLast(val);
        }else{
            //利用方法找到前驱，前驱在index-1的位置
            doubleNode  prev=findNode(index-1);
            doubleNode node=new doubleNode(val);
            node.next=prev.next;
            prev.next.prev=node;
            node.prev=prev;
            prev.next=node;
            size++;
        }
    }

    /**
     * 双向链表的头插
     * @param val
     */
    public void addFirst(int val){
        doubleNode node=new doubleNode(val);
        //判断链表是否为空
        if (head==null){
            head=tail=node;
        }else{
            node.next=head;
            head.prev=node;
            head=node;
        }
        size++;
    }


    /**
     * 双向链表的尾插
     * @param val
     */
    public void addLast(int val){
        doubleNode node=new doubleNode(val);
        if (head==null){
            head=node;
        }else{
            tail.next=node;
            node.prev=tail;
            tail=node;
        }
        size++;
    }


    public String toString(){
        String ret="";
        for (doubleNode x = head; x!=null; x=x.next){
            ret+=x.val;
            ret+="->";
        }
        ret+=null;
        return ret;
    }
}

class doubleNode{

    int val;            //节点存储的值
    doubleNode next;    //节点的后继
    doubleNode prev;    //节点的前驱

    public doubleNode() {
    }

    public doubleNode(int val) {
        this.val = val;
    }

    public doubleNode(int val, doubleNode next, doubleNode prev) {
        this.val = val;
        this.next = next;
        this.prev = prev;
    }
}